Nếu input được đưa như một thủ tục con là để tìm f, bài toán có thể giải đơn giản dùng chỉ λ + μ {\displaystyle \lambda +\mu } lần tính hàm, bằng cách tính chuỗi giá trị x i {\displaystyle x_{i}} dùng một cấu trúc dữ liệu như bảng băm để lưu các giá trị này và kiểm tra xem các giá trị sau đã được lưu chưa. Tuy nhiên, độ phức tạp bộ nhớ tỉ lệ thuận với λ + μ {\displaystyle \lambda +\mu } , lớn không cần thiết. Do đó nghiên cứu trong khu vực này tập trung vào hai mục tiêu: dùng ít bộ nhớ hơn thuật toán trên và tìm thuật toán con trỏ dùng ít số lần kiểm tra hơn.

Thuật toán rùa và thỏ của Floyd

Thuật toán tìm chu trình của Floyd là thuật toán con trỏ dùng hai con trỏ, di chuyển trên cùng một chuỗi với tốc độ khác nhau. Nó cũng được gọi là "thuật toán rùa và thỏ", dựa trên câu chuyện ngụ ngôn của Aesop.

Thuật toán được đặt tên theo Robert W. Floyd, người được công nhận bởi Donald Knuth.[2][3] Tuy nhiên, thuật toán không xuất hiện trong các bài của Floyd, và do đó đây có thể là quy kết nhầm: Floyd mô tả các thuật toán liệt kê toàn bộ các chu trình đơn trong một đồ thị có hướng trong tờ nghiên cứu năm 1967,[4] nhưng tờ báo đó không mô tả bài toán tìm chu trình với đồ thị hàm ở đây. Thậm chí, theo lời của Knuth (vào năm 1969), quy nó về Floyd mà không trích dẫn.[5]

Yếu tố quan trọng trong thuật toán như sau. Nếu có một chu trình, thì, với bất kỳ i ≥ μ và k ≥ 0, xi = xi + kλ, với λ là độ dài vòng lặp cần tìm và μ là vị trí của phần tử đầu tiên trong chu trình. Dựa trên đây, ta có thể chứng minh i = kλ ≥ μ với một vài số k khi và chỉ khi xi = x2i. Như vậy, thuật toán chỉ cần kiểm tra các giá trị lặp lại dưới dạng đặc biệt trên, với một con trỏ để cách gấp đôi từ vị trí xuất phát, để tìm chu kỳ ν cho một lần lặp là bội của λ. Một khi ν được tìm thấy, thuật toán tìm ngược lại từ lúc ban đầu để tìm giá trị đầu tiên xμ trong chuỗi, khi biết rằng λ là ước của ν và do đó xμ = xμ + v. Cuối cùng, một khi μ đã được biết, bài toán trở nên đơn giản trong việc tìm độ dài λ cho chu trình lặp lại ngắn nhất, bằng việc tìm vị trí đầu tiên của μ + λ sao cho xμ + λ = xμ.

Thuật toán do đó dùng hai con trỏ, con trỏ đầu tiên (con rùa) nằm tại xi, và con còn lại (con trỏ) nằm tại x2i. Trong mỗi bước của thuật toán, tăng i bởi một, di chuyển con rùa một bước phía trước và con thỏ hai bước phía trước trong chuỗi, rồi so sánh giá trị chuỗi ở hai con trỏ này. Giá trị nhỏ nhất của i > 0 sao cho rùa và thỏ đều trỏ vào cùng một giá trị là giá trị ν cần tìm.

Đoạn code Python sau mô tả ý tưởng thuật toán trên:

def floyd(f, x0):    # Main phase of algorithm: finding a repetition x_i = x_2i.    # The hare moves twice as quickly as the tortoise and    # the distance between them increases by 1 at each step.    # Eventually they will both be inside the cycle and then,    # at some point, the distance between them will be    # divisible by the period λ.    tortoise = f(x0) # f(x0) is the element/node next to x0.    hare = f(f(x0))    while tortoise != hare:        tortoise = f(tortoise)        hare = f(f(hare))      # At this point the tortoise position, ν, which is also equal    # to the distance between hare and tortoise, is divisible by    # the period λ. So hare moving in circle one step at a time,     # and tortoise (reset to x0) moving towards the circle, will     # intersect at the beginning of the circle. Because the     # distance between them is constant at 2ν, a multiple of λ,    # they will agree as soon as the tortoise reaches index μ.    # Find the position μ of first repetition.        mu = 0    tortoise = x0    while tortoise != hare:        tortoise = f(tortoise)        hare = f(hare)   # Hare and tortoise move at same speed        mu += 1     # Find the length of the shortest cycle starting from x_μ    # The hare moves one step at a time while tortoise is still.    # lam is incremented until λ is found.    lam = 1    hare = f(tortoise)    while tortoise != hare:        hare = f(hare)        lam += 1     return lam, mu

Thuật toán chỉ dùng con trỏ để lưu và sao chép giá trị, tính giá trị hàm và kiểm tra bằng nhau, do đó nó thỏa mãn yêu cầu của thuật toán con trỏ.Thuật toán dùng O(λ + μ) số phép tính trên, và O(1) bộ nhớ.[6]

Thuật toán của Brent

Richard P. Brent mô tả một thuật toán tìm chu trình khác, giống thuật toán rùa và con thỏ, chỉ cần hai con trỏ để duyệt dãy số.[7] Tuy nhiên, nó dựa theo nguyên tắc khác: tìm giá trị lũy thừa bậc hai nhỏ nhất 2i mà lớn hơn cả λ và μ. Với i = 0, 1, 2, ..., thuật toán so sánh x2i−1 với mỗi giá trị phần tử tiếp theo cho đến khi gặp lũy thừa bậc hai tiếp theo, dừng khi nó gặp một cặp bằng nhau. Thuật toán có hai ưu thế so với thuật toán rùa và con thỏ: nó tìm đúng và trực tiếp giá trị λ của chu trình, thay vì phải tìm nó trong đoạn mã sau, và các bước của nó chỉ cần một phép tính f hơn là 3.[8]

Đoạn code python sau mô tả lại ý tưởng trên.

def brent(f, x0):    # main phase: search successive powers of two    power = lam = 1    tortoise = x0    hare = f(x0)  # f(x0) is the element/node next to x0.    while tortoise != hare:        if power == lam:  # time to start a new power of two?            tortoise = hare            power *= 2            lam = 0        hare = f(hare)        lam += 1    # Find the position of the first repetition of length λ    tortoise = hare = x0    for i in range(lam):    # range(lam) produces a list with the values 0, 1, ... , lam-1        hare = f(hare)    # The distance between the hare and tortoise is now λ.    # Next, the hare and tortoise move at same speed until they agree    mu = 0    while tortoise != hare:        tortoise = f(tortoise)        hare = f(hare)        mu += 1     return lam, mu

Giống thuật toán rùa và thỏ, đây là thuật toán con trỏ dùng O(λ + μ) lần kiểm tra và tính hàm cùng với O(1) bộ nhớ. Đồng thời cũng không quá khó để chứng minh rằng số lần tính hàm không bao giờ cao hơn số lần tính trong thuật toán của Floyd. Brent cho rằng, trên trung bình, thuật toán tìm chu trình của ông chạy khoảng 36% nhanh hơn so với cái của Floyd và nó đẩy tốc độ cho thuật toán Pollard rho bởi tầm 24%. Ông cũng xét phân tích trung bình cho phiên bản ngẫu nhiên của thuật toán trong đó dãy chỉ số xét bởi con trỏ chậm hơn không phải lũy thừa bậc hai như thường, mà là bội ngẫu nghiên của lũy thừa bậc hai. Mặc dù ông định áp dụng chủ yếu cho các thuật toán phân tích số nguyên, Brent cũng có xét tới các ứng dụng cho việc kiểm nghiệm các bộ sinh số giả ngẫu nhiên.[7]